动态规划中篇：爬楼梯
作者：alg-flody
编辑：Emily
请点击上面公众号，免费订阅。
主要推送关于对算法的思考以及应用的消息。培养思维能力，注重过程，挖掘背后的原理，刨根问底。本着严谨和准确的态度，目标是撰写实用和启发性的文章，欢迎您的关注。
01
—
你会学到什么？
在前面的两个推送：
我们通过两个实际问题，《装水做多的容器》和《括号知多少》，初步对动态规划有了一个初步了解。
在本推送中，我们将解决以下两个问题：
动态规划牺牲空间换来了什么？
动态规划如何提升时间性能的？
再举动态规划的一个实际例子
02
—
动态规划相关理论
动态规划的定义
动态规划的英文名称为：dynamic programming，接下来看下《Introduction to algorithms》对动态规划的定义：
A dynamic-programming algorithm solves each subsubproblem just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every time it solves each subsubproblem.
翻译过来：
动态规划算法解决每一个子问题，仅一次，然后保存子问题的结果到内存表中，以此来避免对子问题的重复计算。
两种实现方法
top-down with memoization 使用内存自顶向下。保存子问题的结果，之后在求解某个子问题时，若其用到的某个子问题且已经保存了结果，直接返回。
bottom-up method 在求某个子问题时，会依赖已经求出的更小的子问题的解。
第一种方法符合平常的思维模式，第二种和第一种有点反过来的意思。
03
—
动态规划好在哪里
在上一推送中，给出了一堆括号，其中某个子字符括号串是无效的，然后要求最长有效串。 动态规划：括号知多少
如果采取穷举的方法，时间复杂度会达到 O(n^2)，但是这种方法的空间复杂度却为 O(1) 。
为了降低时间复杂度，采取了动态规划算法，使得时间复杂度降为 O(n)，还记得为此付出的代价吗？
是的，空间复杂度达到了O(n)，与穷举相比。
因此，动态规划法，通过牺牲空间，换来了时间效率，这称作 time-memory trade-off 。
需要弄明白的是，动态规划通过牺牲空间，是如何获得执行效率的呢？
这个问题便是动态规划的核心所在，它将某个子问题的计算结果保存到这个内存表中，为之后的问题提供服务，以此来提升执行效率。
04
—
爬楼梯
今天介绍的这个实际问题，是动态规划比较容易理解的实际应用例子之一，请看下面的问题描述：
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
意思是说，每次你可以爬1个或2个台阶，问爬到第 n 个台阶，一共有多少种不同的方法。
例子1：
爬到第2个台阶，共有2种方法，1. 第一步爬1个，第二步爬1个
2. 第一步爬2个
例子2：
爬到第3个台阶，共有3种方法：1. 第一步，二步，三步分别爬1个
2. 第一步爬1个，第二步爬2个
3. 第一步爬2个，第二步爬1个
这个问题可以明显分解为一系列子问题，它包括最优解可以被构建，通过子问题的最优解，可以用动态规划解决这个问题。
一个人到达第 i 层楼底包括两种方法：
选择从第 i-1 层再爬1步到
选择从第 i-2 层再爬2步到
因此，如果用 dp[i] 表示达到第 i 层楼梯的所有方法，那么它进一步等于到达第 i-1 层楼梯的方法加上到达第 i-2 层楼梯的方法的和，即
dp[i] = dp[i-1] + dp[i-2]
有了这个递推公式，自然代码就好写了，如下所示：
public int climbStairs(int n){
if( n==1) return 1;
int[] dp = new int[n+1];
dp[1] = 1;
dp[2] = 2;
for(int i=3; i<=n; i++)
dp[i] = dp[i-1] + dp[i-2];
return dp[n];
}
06
—
总结
在爬楼梯这个实际问题中，看到了动态规划的典型特征，用到了O(n)的空间复杂度，记录已经算过的爬到第i-2层和第i-1层的解，然后通过递推公式得到爬到第i层的解。
算法的时间和空间复杂度都为 O(n) 。
请记住：每天一小步，日积月累一大步！
欢迎关注《算法channel》公众号
主要推送关于对算法的思考以及应用的消息。培养思维能力，注重过程，挖掘背后的原理，刨根问底。本着严谨和准确的态度，目标是撰写实用和启发性的文章，欢迎您的关注。